{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #House Robber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: rob"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #打家劫舍"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，<strong>如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警</strong>。</p>\n",
    "\n",
    "<p>给定一个代表每个房屋存放金额的非负整数数组，计算你<strong> 不触动警报装置的情况下 </strong>，一夜之内能够偷窃到的最高金额。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[1,2,3,1]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。\n",
    "     偷窃到的最高金额 = 1 + 3 = 4 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>[2,7,9,3,1]\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。\n",
    "     偷窃到的最高金额 = 2 + 9 + 1 = 12 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 100</code></li>\n",
    "\t<li><code>0 <= nums[i] <= 400</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [house-robber](https://leetcode.cn/problems/house-robber/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [house-robber](https://leetcode.cn/problems/house-robber/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,1]', '[2,7,9,3,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipChess(self, chessboard: List[str]) -> int:\n",
    "        m, n = len(chessboard), len(chessboard[0])\n",
    "        def judge(chessboard: List[List[str]], x: int, y: int, dx: int, dy: int) -> bool:\n",
    "            x += dx\n",
    "            y += dy\n",
    "            while 0 <= x < len(chessboard) and 0 <= y < len(chessboard[0]):\n",
    "                if chessboard[x][y] == \"X\":\n",
    "                    return True\n",
    "                elif chessboard[x][y] == \".\":\n",
    "                    return False\n",
    "                x += dx\n",
    "                y += dy\n",
    "            return False\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/fHi6rV/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "        def bfs(chessboard, px, py):\n",
    "            cnt = 0\n",
    "            chessboard = [list(row) for row in chessboard]\n",
    "            q = deque([(px, py)])\n",
    "            chessboard[px][py] = 'X'\n",
    "            while q:\n",
    "                x, y = q.popleft()\n",
    "                for dx in (-1, 0, 1):\n",
    "                    for dy in (-1, 0, 1):\n",
    "                        if dx == dy == 0:\n",
    "                            continue\n",
    "                        if judge(chessboard, x, y, dx, dy):\n",
    "                            tx = x + dx\n",
    "                            ty = y + dy\n",
    "                            while chessboard[tx][ty] != 'X':\n",
    "                                cnt += 1\n",
    "                                q.append((tx, ty))\n",
    "                                chessboard[tx][ty] = 'X'\n",
    "                                tx += dx\n",
    "                                ty += dy\n",
    "            return cnt\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if chessboard[i][j] == '.':\n",
    "                    ans = max(ans, bfs(chessboard, i, j))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "\n",
    "class MyCalendar:\n",
    "    def __init__(self):\n",
    "        self.booked = SortedDict()\n",
    "\n",
    "    def book(self, start: int, end: int) -> bool:\n",
    "        i = self.booked.bisect_left(end)\n",
    "        if i == 0 or self.booked.items()[i - 1][1] <= start:\n",
    "            self.booked[start] = end\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/fi9suh/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:\n",
    "        n = len(books)\n",
    "        f = [0] + [inf] * n  # 在前面插入一个状态表示 dfs(-1)=0\n",
    "        for i in range(n):\n",
    "            max_h, left_w = 0, shelf_width\n",
    "            for j in range(i, -1, -1):\n",
    "                left_w -= books[j][0]\n",
    "                if left_w < 0: break  # 空间不足，无法放书\n",
    "                max_h = max(max_h, books[j][1])  # 从 j 到 i 的最大高度\n",
    "                f[i + 1] = min(f[i + 1], f[j] + max_h)\n",
    "        return f[n]  # 翻译自 dfs(n-1)\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/filling-bookcase-shelves/solutions/2240688/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-0vg6/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def goodSubsetofBinaryMatrix(self, grid: List[List[int]]) -> List[int]:\n",
    "\n",
    "        # https://leetcode.cn/problems/find-a-good-subset-of-the-matrix/solutions/2304610/zhi-shang-ju-de-ti-jie-zheng-que-xing-zh-1wju/\n",
    "\n",
    "        \"\"\"\n",
    "        首先要注意到1 <= n <= 5这个数据量，划重点，后面会用到。\n",
    "        为了解释方便，我们称子集大小的一半为“标准”。\n",
    "\n",
    "        1. 首先讨论行子集只有1行时，此情况很简单，因为“标准”为0，所以必须有一行所有元素均为0，否则我们必须考虑选择更多的行来增大“标准”。\n",
    "\n",
    "        2. 当子集行数为2时，“标准”为1，所以要找到两行按列相加后所有元素都小于等于1的行，也就是说必须有两行进行“&”运算后结果为0。\n",
    "        如果找不出这样的两行，我们依然要考虑增加行数来增大“标准”。\n",
    "\n",
    "        3. 当子集行数为3时，其“标准”依然为1，但却要多出一行，完全不用考虑。\n",
    "        不考虑是指，能找到子集为3，为啥不在子集为2的场景时就退出寻找？都是标准为1。多加一行，只会增加列和\n",
    "        不仅行数为3时，所有行数为奇数时都会出现此情况，所以我们只需要考虑行数为偶数的子集。\n",
    "\n",
    "        4. 当子集行数为4时，其“标准”为2，要注意到我们之所以会考虑到将子集取四行，是因为当子集行数为2时，无法找出两行进行“&”运算后结果为0的行，\n",
    "        也就是说，将任意两行按列相加，都至少会出现一个2，那么子集行数为4时，能找出多少个2？\n",
    "        根据组合数的知识，在4行中选2行有6种选法，所以至少会出现6个2，但是1 <= n <= 5，所以必然会有一列之和大于2，\n",
    "        所以当子集行数为2时不行，那么子集行数为4时依然不行。不仅子集行数为4不行，接下来所有更大的偶数都不行,证明方法同理。\n",
    "\n",
    "        所以可以得到结论，如果子集取1行2行都不行，那么就不存在满足条件的取法，所以我们只需要考虑是否有一行元素全部为0，\n",
    "        或者可以找出两行进行“&”运算后结果为0。\n",
    "\n",
    "        \"\"\"\n",
    "        idx = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            mask = 0\n",
    "            for j, x in enumerate(row):\n",
    "                mask |= x << j\n",
    "            idx[mask] = i\n",
    "\n",
    "        # 有一行都是0，满足子集行数为1，”标准“为0的场景\n",
    "        if 0 in idx:\n",
    "            return [idx[0]]\n",
    "\n",
    "        # 两两之间加起来不大于1，满足子集行数2，”标准“为1的场景\n",
    "        for x, i in idx.items():\n",
    "            for y, j in idx.items():\n",
    "                if (x & y) == 0:\n",
    "                    return sorted([i, j])\n",
    "        \n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findAllRecipes(self, recipes: List[str], ingredients: List[List[str]], supplies: List[str]) -> List[str]:\n",
    "            \n",
    "        g = defaultdict(list)\n",
    "        deg = {}\n",
    "        for r, ing in zip(recipes, ingredients):\n",
    "            for s in ing:\n",
    "                g[s].append(r)  # 从这道菜的原材料向这道菜连边\n",
    "            deg[r] = len(ing)\n",
    "        ans = []\n",
    "        q = deque(supplies)  # 拓扑排序（用初始原材料当队列）\n",
    "        while q:\n",
    "            for r in g[q.popleft()]:\n",
    "                deg[r] -= 1\n",
    "                if deg[r] == 0:  # 这道菜的所有原材料我们都有\n",
    "                    q.append(r)\n",
    "                    ans.append(r)\n",
    "        return ans\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/find-all-possible-recipes-from-given-supplies/solutions/1176904/go-tuo-bu-pai-xu-by-endlesscheng-lnlg/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob_helper(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0: return 0\n",
    "        if len(nums) <= 2: return max(nums)\n",
    "        \n",
    "        rob_list = [nums[0], max(nums[:2])]\n",
    "        for i in range(2, len(nums)):\n",
    "            rob_list.append(max(rob_list[i-1], nums[i] + rob_list[i-2]))\n",
    "        return rob_list[-1]\n",
    "        \n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0: return 0\n",
    "        if len(nums) <= 3: return max(nums)\n",
    "        \n",
    "        return max(self.rob_helper(nums[:-1]), self.rob_helper(nums[1:]))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef rob(self, nums):\n",
    "\t\t\"\"\"\n",
    "\t\t:type nums: List[int]\n",
    "\t\t:rtype: int\n",
    "\t\t\"\"\"\n",
    "\t\tif len(nums) <= 1:\n",
    "\t\t\treturn nums[0] if nums else 0\n",
    "\t\t\t\n",
    "\t\tdp = [0 for i in range(len(nums))]\n",
    "\t\tdp[0] = nums[0]\n",
    "\t\tfor i in range(1, len(nums) - 1):\n",
    "\t\t\tdp[i] = max(dp[i-1], (0 if i == 1 else dp[i-2] + nums[i]))\n",
    "\t\tres1 = dp[len(nums) - 2]\n",
    "\t\t\n",
    "\t\tdp[0] = 0\n",
    "\t\tfor i in range(1, len(nums)):\n",
    "\t\t\tdp[i] = max(dp[i-1], (nums[i] if i == 1 else dp[i-2] + nums[i]))\n",
    "\t\t\t\n",
    "#\t\tprint(dp[len(nums) - 1])\n",
    "\t\t\n",
    "\t\treturn max(dp[len(nums) - 1], res1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        arr = [0 for _ in range(len(nums) + 2)]\n",
    "        for i in range(len(nums)):\n",
    "            if i == len(nums) - 1:\n",
    "                arr[i + 2] = max(arr[i + 1], nums[i] + self.rerob(nums[1:-2]))\n",
    "            else:\n",
    "                arr[i + 2] = max(arr[i + 1], nums[i] + arr[i])\n",
    "        return arr[-1]\n",
    "\n",
    "\n",
    "    def rerob(self, nums):\n",
    "        arr = [0 for _ in range(len(nums) + 2)]\n",
    "        for i in range(len(nums)):\n",
    "            arr[i + 2] = max(arr[i + 1], nums[i] + arr[i])\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        dp = [[nums[i] if j == i else 0 for j in range(n)] for i in range(n)]\n",
    "        ret = max(nums)\n",
    "        for i in range(n - 1):\n",
    "            for j in range(i + 1, n):\n",
    "                dp[i][j] = max(dp[i][j], dp[i][j-1] if j > i else 0, dp[i+1][j] if j > i else 0, dp[i][j-2] + nums[j] if j - 2 >= i else 0, dp[i+2][j] + nums[i] if i + 2 <= j else 0)\n",
    "        #print(dp, dp[1][n-1], dp[0][n-2])\n",
    "        return max(ret, dp[1][n-1] if n > 1 else 0, dp[0][n-2] if n > 1 else 0)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) == 0: return 0\n",
    "        if len(nums) == 1: return nums[0]\n",
    "        def helper(start, end):\n",
    "            pre1, pre2 = 0, 0\n",
    "            for i in range(start, end+1):\n",
    "                pre1, pre2 = max(pre1, pre2+nums[i]), pre1\n",
    "            return pre1\n",
    "        return max(helper(0, len(nums)-2), helper(1, len(nums)-1))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n == 0: return 0\n",
    "        if n < 4: return max(nums)\n",
    "\n",
    "        first, second = 0, 0\n",
    "        for i in nums[:-1]: \n",
    "            first, second = second, max(first + i, second)\n",
    "            print(first,second)\n",
    "        result = second\n",
    "\n",
    "        first, second = 0, 0\n",
    "        for i in nums[1:]: \n",
    "            first, second = second, max(first + i, second)\n",
    "            print(first,second)\n",
    "        return max(result, second)\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        dp1 = [0]*len(nums)\n",
    "        dp2 = [0]*len(nums)\n",
    "        for i in range(0,len(nums)-1):\n",
    "            if i == 0:\n",
    "                dp1[i] = nums[i]\n",
    "            elif i == 1:\n",
    "                dp1[i] = max(nums[i],nums[i-1])\n",
    "            else:\n",
    "                dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i])\n",
    "        for j in range(1,len(nums)):\n",
    "            if j == 1:\n",
    "                dp2[j] = nums[j]\n",
    "            elif j == 2:\n",
    "                dp2[j] = max(nums[j],nums[j-1])\n",
    "            else:\n",
    "                dp2[j] = max(dp2[j-1],dp2[j-2]+nums[j])\n",
    "        print(dp1,dp2)\n",
    "        return max(dp1[-2],dp2[-1])\n",
    "            \n",
    "        \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return nums[0]\n",
    "        return max(self.helper(0,n-2,nums),self.helper(1,n-1,nums))\n",
    "\n",
    "    # 求[start,end]之间能偷的最大价值\n",
    "    def helper(self, start, end,nums):\n",
    "        n = end - start + 1\n",
    "        memo = [0] * (n + 2)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            memo[i] = max(nums[i+start] + memo[i + 2], memo[i + 1])\n",
    "        return memo[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#nums[begin, end)\n",
    "def rob(nums, begin, end):\n",
    "    size = end - begin\n",
    "    if size == 0:\n",
    "        return 0\n",
    "    if size == 1:\n",
    "        return nums[begin]\n",
    "    if size == 2:\n",
    "        return max(nums[begin], nums[begin + 1])\n",
    "        \n",
    "    pre_include = nums[begin + 1]\n",
    "    pre_total = max(nums[begin], nums[begin + 1])\n",
    "    prepre_total = nums[begin]\n",
    "        \n",
    "    total = -1;\n",
    "\n",
    "    for i in range(begin + 2, end):\n",
    "        include = prepre_total + nums[i]\n",
    "        temp = max(pre_include, include)\n",
    "        pre_include = include\n",
    "        prepre_total = pre_total\n",
    "        pre_total = temp\n",
    "        total = temp\n",
    "    return total\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        size = len(nums)\n",
    "        if size == 0:\n",
    "            return 0\n",
    "        if size < 4:\n",
    "            return max(nums)\n",
    "        a = rob(nums, 1, size) # do not rob #1house\n",
    "        b = nums[0] + rob(nums, 2, size - 1) # rob #1house\n",
    "        return max(a,b)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        if len(nums) == 2:\n",
    "            return max(nums[0], nums[1])\n",
    "        dp1 = [0 for i in range(len(nums))]\n",
    "        dp2 = [0 for i in range(len(nums))]\n",
    "        dp1[0] = nums[0]\n",
    "        dp1[1] = max(nums[0], nums[1])\n",
    "        dp2[0] = nums[1]\n",
    "        dp2[1] = max(nums[1], nums[2])\n",
    "        for i in range(2, len(nums)-1):\n",
    "            dp1[i] = max(dp1[i-2]+nums[i], dp1[i-1])\n",
    "            dp2[i] = max(dp2[i-2]+nums[i+1], dp2[i-1])\n",
    "        return max(max(dp1), max(dp2))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        if len(nums) == 2:\n",
    "            return max(nums[0], nums[1])\n",
    "        dp1 = [0 for i in range(len(nums)-1)]\n",
    "        dp2 = [0 for i in range(len(nums)-1)]\n",
    "        dp1[0] = nums[0]\n",
    "        dp1[1] = max(nums[0], nums[1])\n",
    "        dp2[0] = nums[1]\n",
    "        dp2[1] = max(nums[1], nums[2])\n",
    "        for i in range(2, len(nums)-1):\n",
    "            dp1[i] = max(dp1[i-2]+nums[i], dp1[i-1])\n",
    "            dp2[i] = max(dp2[i-2]+nums[i+1], dp2[i-1])\n",
    "        return max(max(dp1), max(dp2))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        因为是环， 第一间和第二间房子不能同时被偷\n",
    "        情况1： 第一家偷了， 也就是偷 0, i-1 之间的最大金额\n",
    "        情况2： 第一家不偷   也就是偷 1, i 之间的最大金额\n",
    "        情况3： 第一和最后一家都不偷， 也就是偷 1, i-1 之间的最大金额\n",
    "          情况三的选择一定小于情况1 和2， 所以我们只比较情况1，2 结构即可\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        def _rob(rnums):\n",
    "            n = len(rnums)\n",
    "            dp = [0] * (n + 2)\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                dp[i] = max(dp[i + 1], dp[i + 2] + rnums[i])\n",
    "            return dp[0]\n",
    "            \n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        return max(_rob(nums[:len(nums) - 1]), _rob(nums[1:]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) < 4:\n",
    "            return max(nums) \n",
    "\n",
    "        ans = 0\n",
    "        dp = [0] * (len(nums) - 1)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(1, len(nums) - 2):\n",
    "            dp[i+1] = max(dp[i], nums[i+1] + dp[i-1])\n",
    "        ans = max(ans, dp[-1])\n",
    "\n",
    "        dp[0] = nums[1]\n",
    "        dp[1] = max(nums[1], nums[2])\n",
    "        for i in range(2, len(nums) - 1):\n",
    "            dp[i] = max(dp[i-1], nums[i+1] + dp[i-2])\n",
    "        ans = max(ans, dp[-1])\n",
    "        return ans\n",
    "\n",
    "        '''di = {}\n",
    "\n",
    "        def dfs(nums):\n",
    "            if len(nums) == 0:\n",
    "                return 0\n",
    "            if len(nums) == 1:\n",
    "                return nums[0]\n",
    "            if tuple(nums) in di:\n",
    "                return di[tuple(nums)]\n",
    "            ans = nums[0] + dfs(nums[2:-1])\n",
    "            for i in range(1, len(nums)-1):\n",
    "                ans = max(ans, nums[i] + dfs(nums[:i-1] + nums[i+2:]))\n",
    "            ans = max(ans, nums[-1] + dfs(nums[1:-2]))\n",
    "            di[tuple(nums)] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dfs(nums)'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        lastmax1=0\n",
    "        lastmax2=0\n",
    "        size=len(nums)\n",
    "\n",
    "        if size>1:\n",
    "            lis1=[nums[0]]*size\n",
    "            lis2=[nums[-1]]*size\n",
    "            for i in range(1,size):\n",
    "                lis1[i]=max(lis1[i-1], lastmax1+nums[i])\n",
    "                lastmax1=lis1[i-1]\n",
    "                lis2[size-i-1]=max(lis2[size-i], lastmax2+nums[size-i-1])\n",
    "                lastmax2=lis2[size-i]\n",
    "            return max(lis1[-2], lis2[1])\n",
    "        elif size==1:\n",
    "            return nums[0]\n",
    "        else:\n",
    "            return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:return 0\n",
    "        if len(nums) == 1:return nums[0]\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        nums1 = nums[:-1]\n",
    "        nums2 = nums[1:]\n",
    "\n",
    "        def helper(nums):\n",
    "            if not nums:return 0\n",
    "\n",
    "            n = len(nums)\n",
    "\n",
    "            dp = [0]*n\n",
    "            dp[0] = nums[0]\n",
    "\n",
    "            for i in range(1,n):\n",
    "                if i == 1:\n",
    "                    dp[i] = max(nums[i],nums[i-1])\n",
    "                else:\n",
    "                    dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "            return dp[-1]\n",
    "        \n",
    "        return max(helper(nums1),helper(nums2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: [int]) -> int:\n",
    "        def my_rob(nums):\n",
    "            cur, pre = 0, 0\n",
    "            for num in nums:\n",
    "                cur, pre = max(pre + num, cur), cur\n",
    "            return cur\n",
    "        return max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums) > 1 else nums[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        def my_rob(nums):\n",
    "            if not nums:\n",
    "                return 0\n",
    "            if len(nums) == 1:\n",
    "                return nums[0]\n",
    "            dp = [0 for i in nums]\n",
    "            dp[0] = nums[0]\n",
    "            dp[1] = max(nums[0], nums[1])\n",
    "            for i in range(2, len(nums)):\n",
    "                dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])\n",
    "            return dp[-1]\n",
    "        return max(my_rob(nums[1:]),my_rob(nums[:-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        last1, res1 = 0, 0\n",
    "        for n in nums[1:]:\n",
    "            last1, res1 = res1, max(last1+n, res1)\n",
    "        \n",
    "        last2, res2 = 0, 0\n",
    "        for n in nums[:-1]:\n",
    "            last2, res2 = res2, max(last2+n, res2)\n",
    "        \n",
    "        return max(res1, res2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob_base(self, nums):\n",
    "        length  = len(nums)\n",
    "        if length == 0:\n",
    "            return 0\n",
    "        elif length == 1:\n",
    "            return nums[0]\n",
    "        elif length == 2:\n",
    "            return max(nums[0], nums[1])\n",
    "        dp = list()\n",
    "        dp.extend([nums[0], max(nums[0], nums[1])])\n",
    "        for i in range(2, length):\n",
    "            dp.append(max(dp[-2]+nums[i], dp[-1]))\n",
    "        return max(dp[-1], dp[-2])\n",
    "\n",
    "    def rob(self, nums):\n",
    "            length = len(nums)\n",
    "            if length == 0:\n",
    "                return 0\n",
    "            elif length == 1:\n",
    "                return nums[0]\n",
    "            elif length == 2 or length == 3:\n",
    "                return max(nums)\n",
    "            nums1 = nums[:-1]\n",
    "            nums2 = nums[1:]\n",
    "            return max(self.rob_base(nums1), self.rob_base(nums2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        import functools\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def helper(start, end):\n",
    "            if start > end:\n",
    "                return 0\n",
    "            return max(helper(start + 1, end), # 不抢，去下家\n",
    "                       nums[start] + helper(start + 2, end)) # 抢，去下下家\n",
    "\n",
    "        return max(helper(0, n - 2), helper(1, n - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:return nums[0]\n",
    "        memo = dict()\n",
    "        def dp1(i, current=True):\n",
    "            if i >= len(nums)-1:return 0\n",
    "            t = (i, current)\n",
    "            if t in memo:return memo[t]\n",
    "            memo[t] = 0\n",
    "            if current:\n",
    "                memo[t] = nums[i] + dp1(i+1,False)\n",
    "            else:\n",
    "                memo[t] = max(dp1(i+1,True), dp1(i+1,False))\n",
    "            return memo[t]\n",
    "\n",
    "        memo2 = dict()\n",
    "        def dp2(i, current=False):\n",
    "            if i >= len(nums):return 0\n",
    "            t = (i, current)\n",
    "            if t in memo2:return memo2[t]\n",
    "            memo2[t] = 0\n",
    "            if current:\n",
    "                memo2[t] = nums[i] + dp2(i+1,False)\n",
    "            else:\n",
    "                memo2[t] = max(dp2(i+1,True), dp2(i+1,False))\n",
    "            return memo2[t]\n",
    "        print(dp1(0, True))\n",
    "        print(dp2(0, False))\n",
    "        return max(dp1(0, True), dp2(0, False))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class memoize:\n",
    "    def __init__(self, f):\n",
    "        self.f = f\n",
    "        self.memo = {}\n",
    "\n",
    "    def __call__(self, *args):\n",
    "        key = json.dumps(args)\n",
    "        if not key in self.memo:\n",
    "            self.memo[key] = self.f(*args)\n",
    "        return self.memo[key]\n",
    "\n",
    "@memoize\n",
    "def stole_max(c, money_list):\n",
    "    if c > len(money_list) - 1:\n",
    "        return 0\n",
    "    elif c == len(money_list) - 1:\n",
    "        return money_list[c]\n",
    "    elif c == len(money_list) - 2:\n",
    "        return max(money_list[c], money_list[c + 1])\n",
    "    else:\n",
    "        return max(money_list[c] + stole_max(c + 2, money_list),\n",
    "                   money_list[c + 1] + stole_max(c + 3, money_list))\n",
    "\n",
    "\n",
    "def stole_max_new(money_list):\n",
    "    if len(money_list) == 1:\n",
    "        return money_list[0]\n",
    "\n",
    "    money_list_copy = money_list.copy()\n",
    "    money_list_copy.pop(-1)\n",
    "    return max(stole_max(1, money_list), stole_max(0, money_list_copy))\n",
    "\n",
    "class Solution(object):\n",
    "    def rob(self, nums):\n",
    "        return stole_max_new(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 3:\n",
    "            return max(nums)\n",
    "        \n",
    "        nums1 = nums[: -1]\n",
    "        nums2 = nums[1:]\n",
    "        # print(nums2)\n",
    "        dp1 = [0] * (len(nums))\n",
    "        dp2 = [0] * (len(nums))\n",
    "        dp1[1] = nums1[0]\n",
    "        dp2[1] = nums2[0]\n",
    "        # print(dp2[1])\n",
    "\n",
    "        for i in range(1, len(nums1) + 1):\n",
    "            num1 = nums1[i - 1]\n",
    "            dp1[i] = max(dp1[i - 1], dp1[i - 2] + num1)\n",
    "        \n",
    "        for j in range(1, len(nums2) + 1):\n",
    "            num2 = nums2[j - 1]\n",
    "            dp2[j] = max(dp2[j - 1], dp2[j - 2] + num2)\n",
    "            # print(dp2)\n",
    "        return dp1[-1] if dp1[-1] > dp2[-1] else dp2[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        def rob_value(sub_nums):\n",
    "            pre, cur = 0, 0\n",
    "            for num in sub_nums:\n",
    "                cur, pre = max(pre+num, cur), cur\n",
    "            return cur\n",
    "\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        value1 = rob_value(nums[:len(nums)-1])\n",
    "        # print(nums[:len(nums)-1])\n",
    "        value2 = rob_value(nums[1:])\n",
    "        # print(value2)\n",
    "        return max(value1,value2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def helper(self,nums):\n",
    "        size=len(nums)\n",
    "        if size==1:\n",
    "            return nums[0]\n",
    "        elif size==2:\n",
    "            return max(nums[0],nums[1])\n",
    "        dp=[0 for _ in range(size)]\n",
    "        dp[0]=nums[0]\n",
    "        dp[1]=max(nums[0],nums[1])\n",
    "        for i in range(2,size):\n",
    "            dp[i]=max(dp[i-2]+nums[i],dp[i-1])\n",
    "        return dp[size-1]\n",
    "\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        size=len(nums)\n",
    "        if size==0:\n",
    "            return 0\n",
    "        elif size==1:\n",
    "            return nums[0]\n",
    "        elif size==2:\n",
    "            return max(nums[0],nums[1])\n",
    "        return max(self.helper(nums[:size-1]),self.helper(nums[1:size]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums)==1:\n",
    "            return nums[0]\n",
    "        if len(nums)==2:\n",
    "            return max(nums[0],nums[1])\n",
    "        return max(self.rob_method(nums[1:]),self.rob_method(nums[:len(nums)-1]))\n",
    "\n",
    "    def rob_method(self,nums):\n",
    "        dp = [0]*len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[1],nums[0])\n",
    "        for i in range(2,len(nums)):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        return max(dp[-1],dp[-2])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1:return nums[0]\n",
    "        @cache\n",
    "        def dfs(i,last):\n",
    "            if i<0:return 0\n",
    "            if last and i==0:return 0\n",
    "            tmp = max(dfs(i-1,last),dfs(i-2,last)+nums[i])\n",
    "            return tmp\n",
    "        return max(dfs(n-1,True),dfs(n-2,False))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return max(nums)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        dp[0][0] = nums[0]\n",
    "        dp[0][1] = max(nums[0],nums[1])\n",
    "        dp[1][1] = nums[1]\n",
    "        for i in range(n):\n",
    "            for j in range(2,n):\n",
    "                if i>j:\n",
    "                    dp[i][j] = float('-inf')\n",
    "                elif i == j:\n",
    "                    dp[i][i] = nums[i]\n",
    "                else:\n",
    "                    dp[i][j] = max(dp[i][j-1], dp[i][j-2]+nums[j] if (i>0 or j < n-1) else float('-inf'))\n",
    "        return max(dp[i][n-1] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "\n",
    "            return max(nums[0],self.helper(nums[1:]), self.helper(nums[:-1]))\n",
    "\n",
    "    def helper(self, nums):\n",
    "        rob1,rob2=0,0\n",
    "        for n in nums:\n",
    "            temp=max(rob1+n,rob2)\n",
    "            rob1=rob2\n",
    "            rob2=temp\n",
    "        return rob2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getmaxmoney(self,nums):\n",
    "        if len(nums)<1:return 0\n",
    "        elif len(nums)<2:return nums[0]\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0],nums[1])\n",
    "        for i in range(2,len(nums)):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        return dp[len(nums)-1]\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 1:\n",
    "            return 0\n",
    "        elif len(nums) < 2:\n",
    "            return nums[0]\n",
    "        return max(self.getmaxmoney(nums[:-1]),self.getmaxmoney(nums[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        def rob1(nums: List[int]) -> int:\n",
    "            f0 = f1 = 0\n",
    "            for n in nums:\n",
    "                f0, f1 = f1, max(f1, f0 + n)\n",
    "            \n",
    "            return f1\n",
    "        \n",
    "        return max(nums[0] + rob1(nums[2:-1]), rob1(nums[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "#     def rob(self, root: TreeNode) -> int:\n",
    "#         if root is None: return 0\n",
    "#         if root.left is None and root.right is None: return root.val\n",
    "        \n",
    "#         queue = collections.deque([root]) \n",
    "#         rob_list = []\n",
    "#         while queue:\n",
    "#             temp = 0\n",
    "#             for _ in range(len(queue)):\n",
    "#                 curr = queue.popleft()\n",
    "#                 temp += curr.val\n",
    "#                 if curr.left is not None:\n",
    "#                     queue.append(curr.left)\n",
    "#                 if curr.right is not None:\n",
    "#                     queue.append(curr.right)\n",
    "#             rob_list.append(temp)\n",
    "        \n",
    "#         print(rob_list)\n",
    "#         if len(rob_list) == 2: return max(rob_list)\n",
    "#         val_list = [rob_list[0], max(rob_list[:2])]\n",
    "#         for i in range(2, len(rob_list)):\n",
    "#             val_list.append(max(val_list[i-1], rob_list[i] + val_list[i-2]))\n",
    "#         return val_list[-1]\n",
    "\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "        def robrob(root: TreeNode):\n",
    "            if not root: return 0,0\n",
    "            lmax,lsonmax=robrob(root.left)\n",
    "            rmax,rsonmax=robrob(root.right)\n",
    "            return max(root.val+lsonmax+rsonmax,lmax+rmax),lmax+rmax\n",
    "        return robrob(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0, 0\n",
    "            l1, l2 = dfs(node.left)\n",
    "            r1, r2 = dfs(node.right)\n",
    "            return max(0, node.val) + l2 + r2, max(l1, l2) + max(r1, r2)\n",
    "        return max(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "#         if not root:\n",
    "#             return 0\n",
    "#         res = self.dfs(root)\n",
    "#         return res[0]\n",
    "\n",
    "#     def dfs(self, root):\n",
    "#         temp = [root.val] + [0]\n",
    "#         # temp[0] = root.val\n",
    "#         if not root.left:\n",
    "#             left = self.dfs(root.left)\n",
    "#             temp[1] += left[0]\n",
    "#             temp[0] += left[1]\n",
    "#         if not root.right:\n",
    "#             right = self.dfs(root.right)\n",
    "#             temp[1] += right[0]\n",
    "#             temp[0] += right[1]\n",
    "#         temp[0] = max(temp[0], temp[1])\n",
    "#         return temp\n",
    "        def dfs(root):\n",
    "            # from bottom to top\n",
    "            if not root: return [0, 0] # before layer, no robcurr, robcurr\n",
    "            robleft = dfs(root.left)\n",
    "            robright = dfs(root.right)\n",
    "            norobcurr = robleft[1] + robright[1]\n",
    "            robcurr = max(root.val + robleft[0] + robright[0], norobcurr)\n",
    "            return [norobcurr, robcurr]\n",
    "        return dfs(root)[1]\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        h = {}\n",
    "        def maxroot(root):\n",
    "            if root in h:\n",
    "                return h[root]\n",
    "            if not root:\n",
    "                    return 0\n",
    "            res1 = root.val\n",
    "            res2 = 0\n",
    "            if root.left:\n",
    "                res1 += maxroot(root.left.left)+maxroot(root.left.right)\n",
    "                res2 += maxroot(root.left)\n",
    "            if root.right:\n",
    "                res1 += maxroot(root.right.left)+maxroot(root.right.right)\n",
    "                res2 += maxroot(root.right)\n",
    "            h[root]= max(res1, res2)\n",
    "            return h[root]\n",
    "\n",
    "        return maxroot(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.d = collections.defaultdict()\n",
    "        \n",
    "    def rob(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root in self.d:\n",
    "            return self.d[root]\n",
    "        \n",
    "        cur = 0\n",
    "        if root.left:\n",
    "            cur += self.rob(root.left.left) + self.rob(root.left.right)\n",
    "        if root.right:\n",
    "            cur += self.rob(root.right.left) + self.rob(root.right.right)\n",
    "        \n",
    "        cur = max(root.val + cur, self.rob(root.left) + self.rob(root.right))\n",
    "        self.d[root] = cur\n",
    "        \n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root: 'TreeNode') -> 'int':\n",
    "        skip = {None: 0}\n",
    "        noskip = {None: 0}\n",
    "        \n",
    "        stack, last = [], None\n",
    "        if root:\n",
    "            stack.append(root)\n",
    "            node = root.left\n",
    "        while stack:\n",
    "            if node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = stack[-1]\n",
    "                if node.right and last != node.right:\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    node = stack.pop()\n",
    "                    \n",
    "                    skip[node] = max(noskip[node.left], skip[node.left]) + max(noskip[node.right], skip[node.right])\n",
    "                    noskip[node] = node.val + skip[node.left] + skip[node.right]\n",
    "                    \n",
    "                    last = node\n",
    "                    node = None\n",
    "        \n",
    "        return max(skip[root], noskip[root])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        rtype: int\n",
    "        \"\"\"\n",
    "        if not root:return 0\n",
    "        #1为偷了，2为没偷\n",
    "        dict1={}\n",
    "        dict2={}\n",
    "        #二叉树一般都是用递归解决的，一个房间最终救2个状态，被偷或者不被偷\n",
    "        def rob_max_profit(node):\n",
    "            ii=id(node)\n",
    "            if ii in dict1:\n",
    "                return (dict1[ii],dict2[ii])\n",
    "            if not node.left and not node.right:\n",
    "                dict1[ii]=node.val\n",
    "                dict2[ii]=0\n",
    "            elif not node.left and node.right:\n",
    "                r=rob_max_profit(node.right)\n",
    "                dict1[ii]=node.val+r[1]\n",
    "                dict2[ii]=max(r)\n",
    "            elif not node.right and node.left:\n",
    "                l=rob_max_profit(node.left)\n",
    "                dict1[ii]=node.val+l[1]\n",
    "                dict2[ii]=max(l)\n",
    "            else:\n",
    "                l,r=rob_max_profit(node.left),rob_max_profit(node.right)\n",
    "                dict1[ii]=node.val+l[1]+r[1]\n",
    "                dict2[ii]=max(l)+max(r)\n",
    "            return (dict1[ii],dict2[ii])\n",
    "        return max(rob_max_profit(root))\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = [(0, root)]\n",
    "        result = {None: (0, 0)}\n",
    "        while stack:\n",
    "            rob, node = stack.pop()\n",
    "            if not node:\n",
    "                continue\n",
    "                \n",
    "            if not rob:\n",
    "                stack.extend([(1, node), (0, node.right), (0, node.left)])\n",
    "            else:\n",
    "                result[node] = (result[node.left][1] + result[node.right][1] + node.val,\\\n",
    "                               max(result[node.left]) + max(result[node.right]))\n",
    "        return max(result[root])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        mem = dict()\n",
    "        check = self._rob(root, \"\", mem)\n",
    "        return max(check[0], check[1])\n",
    "\n",
    "    def _rob(self, root, path, mem):\n",
    "        if not root:\n",
    "            return [0, 0]\n",
    "\n",
    "        if path in mem:\n",
    "            return mem[path]\n",
    "\n",
    "        l, r = self._rob(root.left, path + 'l', mem), self._rob(root.right, path + 'r', mem)\n",
    "        mem[path] = l[1] + r[1] + root.val, max(l) + max(r)\n",
    "        return mem[path]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "        def search(node):\n",
    "            if node is None:\n",
    "                return 0, 0\n",
    "            else:\n",
    "                left_val, left_lower_val = search(node.left)\n",
    "                right_val, right_lower_val = search(node.right)\n",
    "                max_lower_val = left_val + right_val\n",
    "                max_val = max(max_lower_val, node.val + left_lower_val + right_lower_val)\n",
    "                return max_val, max_lower_val\n",
    "        ans, _ = search(root)\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "        return max(self._rob(root))\n",
    "\n",
    "    def _rob(self, root: TreeNode) -> (int, int):\n",
    "        '''\n",
    "        返回偷根和不偷根两种情况下的最大值\n",
    "        偷根的话就是左右子树不偷根的和加上自己的值\n",
    "        不偷根的话就是左右子树偷根和不偷根的最大值相加\n",
    "        '''\n",
    "        if not root:\n",
    "            return 0, 0\n",
    "        else:\n",
    "            s_l, n_s_l = self._rob(root.left)\n",
    "            s_r, n_s_r = self._rob(root.right)\n",
    "            return root.val + n_s_l + n_s_r, max(s_l, n_s_l) + max(s_r, n_s_r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "        def dp(root):\n",
    "            if not root:\n",
    "                return [0, 0]\n",
    "            left = dp(root.left)\n",
    "            right = dp(root.right)\n",
    "            rob = root.val + left[0] + right[0]\n",
    "            not_rob = max(left[0], left[1]) + max(right[0], right[1])\n",
    "            return [not_rob, rob]\n",
    "        res = dp(root)\n",
    "        return max(res[0], res[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "        a = self.helper(root)   # a 是一个二维数组, 为root的[偷值, 不偷值]\n",
    "        return max(a[0], a[1])  # 返回两个值的最大值, 此值为小偷最终获得的总值\n",
    "    \n",
    "    # 参数为root节点, helper方法输出一个二维数组：root节点的[偷值, 不偷值]\n",
    "    def helper(self, root):     # 递归结束条件：root为空, 输出 [0, 0]\n",
    "        if not root:\n",
    "            return [0, 0]\n",
    "        left = self.helper(root.left)   # left是一个二维数组, 为 root 左侧子节点的[偷值, 不偷值]\n",
    "        right = self.helper(root.right) # right也是一个二维数组, 为root右侧子节点的[偷值, 不偷值]\n",
    "        robValue = left[1] + right[1] + root.val    # root 的偷值\n",
    "        skipValue = max(left[0], left[1]) + max(right[0], right[1]) # root 的不偷值\n",
    "        return [robValue, skipValue]    # 输出小偷可获得的最大金额"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "        def dfs(newroot):\n",
    "            if not newroot:\n",
    "                return [0,0]\n",
    "            left=dfs(newroot.left)\n",
    "            right=dfs(newroot.right)\n",
    "            robvalue=newroot.val+left[1]+right[1]\n",
    "            norobvalue=max(left[0],left[1])+max(right[0],right[1])\n",
    "            return [robvalue,norobvalue]\n",
    "        \n",
    "        res=dfs(root)\n",
    "        return max(res[0],res[1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "        def rob_iter(root):\n",
    "            if not root: return 0, 0\n",
    "            left = rob_iter(root.left)\n",
    "            right = rob_iter(root.right)\n",
    "            v1 = left[1] + right[1] + root.val\n",
    "            v2 = max(left) + max(right)\n",
    "            return v1, v2\n",
    "        return max(rob_iter(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "\n",
    "        dp = {}\n",
    "        def robTree(root: TreeNode):\n",
    "            if root is None:\n",
    "                return 0\n",
    "\n",
    "            if root in dp:\n",
    "                return dp[root]\n",
    "            \n",
    "            do_it = root.val\n",
    "            if root.left is not None:\n",
    "                do_it += robTree(root.left.left) + robTree(root.left.right)\n",
    "\n",
    "            if root.right is not None:\n",
    "                do_it += robTree(root.right.left) + robTree(root.right.right)\n",
    "\n",
    "            not_do = robTree(root.left) + robTree(root.right)\n",
    "\n",
    "            dp[root] = max(do_it, not_do)\n",
    "            return dp[root]\n",
    "\n",
    "        return robTree(root)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "        \n",
    "        dict_visited = collections.defaultdict(int)\n",
    "        \n",
    "        def dfs(node):\n",
    "\n",
    "            if dict_visited[node]:\n",
    "                return dict_visited[node]\n",
    "\n",
    "            if not node:\n",
    "                return 0\n",
    "\n",
    "            rs_left_left, rs_left_right, rs_right_left, rs_right_right = 0, 0, 0, 0\n",
    "            if node.left:\n",
    "                rs_left_left = dfs(node.left.left)\n",
    "                rs_left_right = dfs(node.left.right)\n",
    "            if node.right:\n",
    "                rs_right_left = dfs(node.right.left)\n",
    "                rs_right_right = dfs(node.right.right)\n",
    "\n",
    "            rs_left = dfs(node.left)\n",
    "            rs_right = dfs(node.right)          \n",
    "\n",
    "            rs1 = sum([node.val, rs_left_left, rs_left_right, rs_right_left, rs_right_right])\n",
    "            rs2 = sum([rs_left, rs_right])\n",
    "            \n",
    "            rs = max(rs1, rs2)\n",
    "            dict_visited[node] = rs\n",
    "            return rs\n",
    "            \n",
    "        return dfs(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "\n",
    "\n",
    "        def helper(node):\n",
    "            if node is None:\n",
    "                return 0, 0\n",
    "            left_steal, left_no = helper(node.left)\n",
    "            right_steal, right_no = helper(node.right)\n",
    "            return node.val + left_no + right_no, max(left_steal, left_no) + max(right_steal, right_no)\n",
    "\n",
    "        return max(helper(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: TreeNode) -> int:\n",
    "        def _rob(node):\n",
    "            if not node: return 0, 0\n",
    "            ly, ln = _rob(node.left)\n",
    "            ry, rn = _rob(node.right)\n",
    "            return node.val + ln + rn, max(ly, ln) + max(ry, rn)\n",
    "        return max(_rob(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        res = list(self.houserobber(root))\n",
    "        return max(res)\n",
    "    def houserobber(self, root):\n",
    "        #定义：输入一颗树，返回选择根和不选根的最大金额[yes, no]\n",
    "        if not root: \n",
    "            return [0,0] \n",
    "        left = self.houserobber(root.left)\n",
    "        right = self.houserobber(root.right)\n",
    "        \n",
    "        yes = left[1] + right[1] + root.val\n",
    "        no = max(left) + max(right)\n",
    "        return [yes, no]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "'''\n",
    "status related. -> dp -> f(node) - max(f(nxt_lvl), f(next_next_lvl) + node.val)\n",
    "'''\n",
    "# class Solution:\n",
    "#     def rob(self, root: Optional[TreeNode]) -> int:\n",
    "#         return self.max_gain(root)\n",
    "        \n",
    "\n",
    "#     @lru_cache(None)\n",
    "#     def max_gain(self, node):\n",
    "#         if not node:\n",
    "#             return 0\n",
    "#         nxt_lvl = self.max_gain(node.left) + self.max_gain(node.right)\n",
    "#         nxt_nxt_lvl = node.val\n",
    "#         if node.left:\n",
    "#             nxt_nxt_lvl += (self.max_gain(node.left.left) + self.max_gain(node.left.right))\n",
    "#         if node.right:\n",
    "#             nxt_nxt_lvl += (self.max_gain(node.right.left) + self.max_gain(node.right.right))\n",
    "#         return max(nxt_lvl, nxt_nxt_lvl)\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        return max(self.dfs(root))\n",
    "\n",
    "    def dfs(self, node):\n",
    "        if not node:\n",
    "            return (0, 0)\n",
    "        unrelated_sum = node.val\n",
    "        realted_sum = 0\n",
    "        for nxt_node in (node.left, node.right):\n",
    "            report_rel, report_un = self.dfs(nxt_node)\n",
    "            unrelated_sum += report_rel\n",
    "            realted_sum += max(report_un, report_rel)\n",
    "        # print(node.val, realted_sum, unrelated_sum)\n",
    "        return (realted_sum, unrelated_sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0, 0\n",
    "            \n",
    "\n",
    "            left_no_steal, left_steal = dfs(root.left)\n",
    "            right_no_steal, right_steal = dfs(root.right)\n",
    "\n",
    "            steal = left_no_steal + right_no_steal +root.val\n",
    "            no_steal = max(left_no_steal, left_steal) + max(right_steal, right_no_steal)\n",
    "            return no_steal, steal\n",
    "        return max(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        # 树形dp 根节点的取舍上需要比较判断，所以遍历函数需要返回取和不取该节点的最高金额\n",
    "        # k1.后序遍历，需要根据左右子树的遍历结果来确定根节点的操作逻辑\n",
    "        # k2.避免重复遍历\n",
    "        def traverse(node):\n",
    "            if node == None: return [0,0]\n",
    "            left = traverse(node.left)\n",
    "            right = traverse(node.right)\n",
    "            # 取root\n",
    "            withroot = node.val + left[0] + right[0]\n",
    "            # 不取root\n",
    "            without = max(left[0],left[1]) + max(right[0],right[1])\n",
    "            return [without,withroot]\n",
    "        withroot,without = traverse(root)\n",
    "        return max(withroot,without)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.recorded = {}\n",
    "\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if root in self.recorded:\n",
    "            return self.recorded[root]\n",
    "        val1 = root.val\n",
    "        if root.left:val1 += self.rob(root.left.left) + self.rob(root.left.right)\n",
    "        if root.right:val1 += self.rob(root.right.left) + self.rob(root.right.right)\n",
    "        val2 = self.rob(root.left) + self.rob(root.right)\n",
    "        self.recorded[root] = max(val1,val2)\n",
    "        return max(val1, val2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        res = self.helper(root)\n",
    "        return max(res[0], res[1])\n",
    "\n",
    "    def helper(self, root):\n",
    "        if root == None: return [0, 0]\n",
    "        res_cur = [0, 0] # 0 no rob, 1 rob\n",
    "\n",
    "        left = self.helper(root.left)\n",
    "        right = self.helper(root.right)\n",
    "\n",
    "        res_cur[0] = max(left[0], left[1]) + max(right[0], right[1])\n",
    "        res_cur[1] = left[0] + right[0] + root.val\n",
    "        return res_cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def robtree(self,root):\n",
    "        if not root:\n",
    "            return (0,0)\n",
    "        left = self.robtree(root.left)\n",
    "        right = self.robtree(root.right)\n",
    "        val1 = root.val + left[0] + right[0]\n",
    "        val2 = max(left[0],left[1]) + max(right[0],right[1])\n",
    "        return (val2,val1)\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        result = self.robtree(root)\n",
    "        return max(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        return max(self.traversal(root))\n",
    "    def traversal(self,root):\n",
    "        if not root:\n",
    "            return (0,0)\n",
    "        left = self.traversal(root.left)\n",
    "        right = self.traversal(root.right)\n",
    "        val1 = root.val + left[0]+right[0]\n",
    "        val2 = max(left[1],left[0])+max(right[0],right[1])\n",
    "        return (val2,val1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = {}\n",
    "\n",
    "    def rob(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "\n",
    "        if root in self.memo:\n",
    "            return self.memo[root]\n",
    "\n",
    "        do_it = root.val\n",
    "        if root.left:\n",
    "            do_it += self.rob(root.left.left) + self.rob(root.left.right)\n",
    "        if root.right:\n",
    "            do_it += self.rob(root.right.left) + self.rob(root.right.right)\n",
    "\n",
    "        not_do = self.rob(root.left) + self.rob(root.right)\n",
    "\n",
    "        res = max(do_it, not_do)\n",
    "        self.memo[root] = res\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.map = {}\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and not root.right:\n",
    "            return root.val\n",
    "        if root in self.map.keys():\n",
    "            return self.map[root]\n",
    "        val1 = root.val\n",
    "        if root.left:\n",
    "            val1+=self.rob(root.left.left)+self.rob(root.left.right)\n",
    "        if root.right:\n",
    "            val1+=self.rob(root.right.left)+self.rob(root.right.right)\n",
    "        val2 = self.rob(root.left)+self.rob(root.right)\n",
    "        self.map[root] = max(val1, val2)\n",
    "        return max(val1, val2)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        @cache\n",
    "        def func(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = func(node.left.left) + func(node.left.right) if node.left else 0\n",
    "            right = func(node.right.left) + func(node.right.right) if node.right else 0\n",
    "            return max(node.val + left+right, func(node.left)+func(node.right))\n",
    "        return func(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        \n",
    "        f = collections.defaultdict(int)\n",
    "        g = collections.defaultdict(int)\n",
    "\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            f[root] = root.val + g[root.left] + g[root.right]\n",
    "            g[root] = max(f[root.left], g[root.left]) + max(f[root.right], g[root.right])\n",
    "        \n",
    "        dfs(root)\n",
    "        return max(f[root], g[root])\n",
    "        \n",
    "        \n",
    "        # res1 = 0\n",
    "        # res2 = 0\n",
    "        # q = collections.deque()\n",
    "        # q.append(root)\n",
    "        # i = 0\n",
    "        # while q:\n",
    "        #     n = len(q)\n",
    "        #     for _ in range(n):\n",
    "        #         node = q.popleft()\n",
    "        #         if i % 2 == 0:\n",
    "        #             res1 += node.val\n",
    "        #         else:\n",
    "        #             res2 += node.val\n",
    "        #         if node.left:\n",
    "        #             q.append(node.left)\n",
    "        #         if node.right:\n",
    "        #             q.append(node.right)\n",
    "        #     i += 1\n",
    "        # return max(res1, res2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    rob_dict = {}\n",
    "\n",
    "\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        rob_val = max(self.rob_current_node(root) ,self.not_rob_current_node(root))\n",
    "        return rob_val\n",
    "\n",
    "    def rob_current_node(self,root: Optional[TreeNode]) ->  int :\n",
    "        if root is None:\n",
    "            return 0\n",
    "        if root in self.rob_dict:\n",
    "            return self.rob_dict[root]\n",
    "        else:\n",
    "            value = root.val + self.not_rob_current_node(root.left) + self.not_rob_current_node(root.right)\n",
    "            self.rob_dict[root] = value\n",
    "            return value\n",
    "\n",
    "    def not_rob_current_node(self,root: Optional[TreeNode]) -> int :\n",
    "        if root is None:\n",
    "            return 0\n",
    "        return max(self.rob_current_node(root.left),self.not_rob_current_node(root.left)) + max(self.rob_current_node(root.right),self.not_rob_current_node(root.right))            \n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# 法1：暴力递归 + 哈希表记忆\n",
    "hashdict = {}\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        money = root.val\n",
    "        if root.left:\n",
    "            hashdict[root.left.left] = self.rob(root.left.left)\n",
    "            hashdict[root.left.right] = self.rob(root.left.right)\n",
    "            money += hashdict[root.left.left] + hashdict[root.left.right]\n",
    "\n",
    "        if root.right:\n",
    "            hashdict[root.right.left] = self.rob(root.right.left)\n",
    "            hashdict[root.right.right] = self.rob(root.right.right)\n",
    "            money += hashdict[root.right.left] + hashdict[root.right.right]\n",
    "        money1 = 0\n",
    "        money1 += hashdict[root.left] if root.left in hashdict else self.rob(root.left)\n",
    "        money1 += hashdict[root.right] if root.right in hashdict else self.rob(root.right)\n",
    "        return max(money, money1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        self.mem = {}\n",
    "        return self.helper(root, 1)\n",
    "    def helper(self, node, can_rob):\n",
    "        if not node:\n",
    "            return 0\n",
    "        if (node, can_rob) in self.mem:\n",
    "            return self.mem[(node, can_rob)]\n",
    "        res1 = res2 = 0\n",
    "        if can_rob:\n",
    "            res1 = node.val\n",
    "            if node.left:\n",
    "                res1 += self.helper(node.left, 0)\n",
    "            if node.right:\n",
    "                res1 += self.helper(node.right, 0)\n",
    "        res2 += self.helper(node.left, 1)\n",
    "        res2 += self.helper(node.right, 1)\n",
    "        res = max(res1, res2)\n",
    "        self.mem[(node, can_rob)] = res\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def rob(self, root: Optional[TreeNode]) -> int:\n",
    "        @cache\n",
    "        def GetF(node):\n",
    "            if node==None:\n",
    "                return 0\n",
    "            res=GetG(node.left)+GetG(node.right)+node.val\n",
    "            return res\n",
    "        @cache\n",
    "        def GetG(node):\n",
    "            if node==None:\n",
    "                return 0\n",
    "            res=max(GetG(node.left),GetF(node.left))+max(GetG(node.right),GetF(node.right))\n",
    "            return res\n",
    "        return max(GetF(root),GetG(root))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCapability(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        def robberNum(x):\n",
    "            dp = [0] * n \n",
    "    \n",
    "            if nums[0] <= x:\n",
    "                dp[0] = 1\n",
    "\n",
    "            if n == 1:\n",
    "                return dp[0]\n",
    "\n",
    "            if n > 1:\n",
    "                dp[1] = 1 if dp[0] or nums[1] <= x else 0\n",
    "\n",
    "            for i in range(2, n):\n",
    "                dp[i] = max(dp[i-1], dp[i-2] + (1 if nums[i] <= x else 0))\n",
    "\n",
    "            return dp[-1]\n",
    "\n",
    "        l = 0\n",
    "        r = max(nums)\n",
    "\n",
    "        while l + 1 < r:\n",
    "            m = l + (r - l) // 2\n",
    "            if robberNum(m) >= k:\n",
    "                r = m\n",
    "            else:\n",
    "                l = m\n",
    "\n",
    "        return r\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # you did not realize it is an dynamic programming problem !!!\n",
    "#         if len(nums) == 0: return 0\n",
    "#         result = []\n",
    "#         while i in range(2):\n",
    "#             for step in range(2, )\n",
    "#             step = \n",
    "#             while step < len(nums)-1:\n",
    "                \n",
    "#         even_num, odd_num = 0, 0\n",
    "#         for i in range(len(nums)):\n",
    "#             if i % 2 == 0:\n",
    "#                 even_num += nums[i]\n",
    "#             else:\n",
    "#                 odd_num += nums[i]\n",
    "                \n",
    "#         return max(even_num, odd_num)\n",
    "        # prev_max, curr_max = 0, 0\n",
    "        # for num in nums:\n",
    "        #     temp = curr_max\n",
    "        #     curr_max = max(prev_max + num, curr_max)\n",
    "        #     prev_max = temp\n",
    "        # return curr_max\n",
    "        \n",
    "        if len(nums) == 0: return 0\n",
    "        if len(nums) == 1: return nums[0]\n",
    "        if len(nums) == 2: return max(nums)\n",
    "        dp = [nums[0], max(nums[0], nums[1])]\n",
    "        for i in range(2, len(nums)):\n",
    "            dp.append(max(dp[i-1], nums[i] + dp[i-2]))\n",
    "        return dp[-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        last,now = 0, 0\n",
    "        for i in nums:\n",
    "            last, now = now, max(now, last+i)\n",
    "        return now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # f(x) = max(f(x-1), x + f(x-2))\n",
    "        arr = [0 for i in range(len(nums)+1)]\n",
    "        for i in range(len(nums)):\n",
    "            arr[i+1] = max(arr[i], nums[i]+arr[i-1])\n",
    "        return arr[-1]\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: 'List[int]') -> 'int':\n",
    "        length=len(nums)\n",
    "        res=0\n",
    "        dp=[0 for x in range(length)]\n",
    "        if(length==0):\n",
    "            return 0\n",
    "        elif(length==1):\n",
    "            dp[0]=nums[0]\n",
    "        elif(length==2):\n",
    "            dp[0]=nums[0]\n",
    "            dp[1]=max(dp[0],nums[1])\n",
    "        else:\n",
    "            i=2\n",
    "            dp[0]=nums[0]\n",
    "            dp[1]=max(dp[0],nums[1])\n",
    "            while(i<length):\n",
    "                dp[i]=max(nums[i]+dp[i-2],dp[i-1])\n",
    "                print(dp[i])\n",
    "                i=i+1\n",
    "        return max(dp)\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef rob(self, nums):\n",
    "\t\t\"\"\"\n",
    "\t\t:type nums: List[int]\n",
    "\t\t:rtype: int\n",
    "\t\t\"\"\"\n",
    "\n",
    "\t\ta, b = 0, 0\n",
    "\t\tfor num in nums:\n",
    "\t\t\ta, b = b, max(a + num, b)\n",
    "\t\treturn b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        \n",
    "        if len(nums)==0:\n",
    "            return 0\n",
    "        elif len(nums)<3:\n",
    "            return max(nums)\n",
    "        else:\n",
    "            score = [0]*len(nums)\n",
    "            score[0] = nums[0]\n",
    "            score[1] = max(nums[0],nums[1])\n",
    "            score[2] = max((nums[0]+nums[2]),nums[1])\n",
    "            for i in range(3,len(nums)):\n",
    "                score[i] = max(score[i-1],(score[i-2]+nums[i]))\n",
    "            return score[-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        sum1 = 0  # 记录n-2出现的最大和\n",
    "        sum2 = 0  # 记录n-1出现的最大和\n",
    "        for i in range(len(nums)):\n",
    "            if i % 2 == 0:\n",
    "                # 比较sum1+nums[i] 和 sum2\n",
    "                if sum1 + nums[i] > sum2:\n",
    "                    sum1 += nums[i]\n",
    "                else:\n",
    "                    sum1 = sum2\n",
    "            else:\n",
    "                # 比较sum2+nums[i] 和 sum1\n",
    "                if sum2 + nums[i] > sum1:\n",
    "                    sum2 += nums[i]\n",
    "                else:\n",
    "                    sum2 = sum1\n",
    "        print(max(sum1, sum2))\n",
    "        return max(sum1, sum2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # Solution timelimit exceeded\n",
    "        # if not nums:\n",
    "        #     return 0\n",
    "        # if len(nums) <= 2:\n",
    "        #     return max(nums)\n",
    "        # elif len(nums) == 3:\n",
    "        #     return max(nums[0] + nums[2], nums[1])\n",
    "        # elif len(nums) == 4:\n",
    "        #     return max(nums[0] + nums[2], nums[1] + nums[3], nums[0] + nums[3])\n",
    "        # return max(nums[0] + self.rob(nums[2:]), nums[1] + self.rob(nums[3:]))\n",
    "        \n",
    "        # Solution quick\n",
    "        # now = last = 0\n",
    "        # for i, n in enumerate(nums):\n",
    "        #     # if i % 2 == 0:\n",
    "        #     #     now = max(now + n, last)\n",
    "        #     # else:\n",
    "        #     #     last = max(now, last + n)\n",
    "        #     now, last = last, max(now + n, last)\n",
    "        # return max(now, last)\n",
    "        \n",
    "        # Solution with dp\n",
    "        # DP formula: f(n) = max(f(n-2)+nums[n-1], f(n-1)), f(0) = nums[0], f(1) = max(nums[0], nums[1])\n",
    "        n = len(nums)\n",
    "        if not n:\n",
    "            return 0\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = nums[0]\n",
    "        for i in range(2, n+1):\n",
    "            dp[i] = max(dp[i-1], nums[i-1]+dp[i-2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        if nums == []:\n",
    "            return 0\n",
    "        dp = [0]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0:\n",
    "                dp[i] = nums[i]\n",
    "            elif i == 1:\n",
    "                dp[i] = max(nums[i], nums[i-1])\n",
    "            else: \n",
    "                dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        #print(dp)\n",
    "        return dp[-1]\n",
    "        \"\"\"\n",
    "        cur = pre = 0\n",
    "        \n",
    "        for i in nums:\n",
    "            pre,cur = cur,max(cur,pre+i)\n",
    "            \n",
    "        return cur "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) <= 0:\n",
    "            return 0\n",
    "        elif len(nums) <= 2:\n",
    "            return max(nums)\n",
    "        else:\n",
    "            tmp = [0 for _ in range(len(nums))]\n",
    "            tmp[0] = nums[0]\n",
    "            tmp[1] = max(nums[0], nums[1])\n",
    "            for i in range(2, len(nums)):\n",
    "                n = nums[i]\n",
    "                tmp[i] = max(n + tmp[i - 2], tmp[i - 1])\n",
    "\n",
    "            return tmp[-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob2(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        if len(nums) == 2:\n",
    "            return max(nums)\n",
    "        \n",
    "        \n",
    "        return max(self.rob(nums[:-1]), self.rob(nums[:-2])+ nums[-1])\n",
    "    \n",
    "    def rob3(self, nums):\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        if len(nums) == 2:\n",
    "            return max(nums)\n",
    "        \n",
    "        maxrob = [nums[0], max(nums[:2])]\n",
    "        \n",
    "        for i in range(2,len(nums)):\n",
    "            p = i%2\n",
    "            maxrob[p]=max(maxrob[1-p], nums[i]+maxrob[p])\n",
    "        \n",
    "        return max(maxrob)\n",
    "    \n",
    "    def rob(self, nums):\n",
    "        pre, now = 0, 0\n",
    "        for n in nums:\n",
    "            pre, now =now, max(now, pre + n)\n",
    "        return now\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.func2(nums)\n",
    "    \n",
    "    def func1(self,nums):\n",
    "        l = len(nums)\n",
    "        if not l:\n",
    "            return 0\n",
    "        s = []\n",
    "        nots = []\n",
    "        for i in range(l):\n",
    "            if i-1 > -1:\n",
    "                s.append(nots[i-1]+nums[i])\n",
    "                nots.append(max(nots[i-1],s[i-1]))\n",
    "            else:\n",
    "                s.append(nums[i])\n",
    "                nots.append(0)\n",
    "        return max(nots[-1],s[-1])\n",
    "    \n",
    "    def func2(self,nums):\n",
    "        l = len(nums)\n",
    "        if not l:\n",
    "            return 0\n",
    "        temp = []\n",
    "        for i in range(l):\n",
    "            a = nums[i]\n",
    "            if i-2 >=0:\n",
    "                a += temp[i-2]\n",
    "            b = 0 \n",
    "            if i -1 >=0:\n",
    "                b = temp[i-1]\n",
    "            temp.append(max(a,b))\n",
    "        return temp[l-1]\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: 'List[int]') -> 'int':\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        money0 = nums[0]\n",
    "        money1 = max(nums[0], nums[1])\n",
    "        for i in range(2, len(nums), 1):\n",
    "            money = max(money1, money0 + nums[i])\n",
    "            money0 = money1\n",
    "            money1 = money\n",
    "        return money1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        dp = [x for x in nums]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(2, len(nums)):\n",
    "            dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        acc = [None] * len(nums)\n",
    "        max_list = [None] * len(nums)\n",
    "        max_acc = 0\n",
    "        for i,n in enumerate(nums):\n",
    "            if i < 2:\n",
    "                acc[i] = n\n",
    "            else:\n",
    "                acc[i] = n + max_list[i-2]\n",
    "            max_acc = max(max_acc, acc[i])\n",
    "            max_list[i] = max_acc\n",
    "        return max_acc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        lenNums = len(nums)\n",
    "        if lenNums == 0:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        for i in range(lenNums):\n",
    "            if i == 0:\n",
    "                a = nums[i]\n",
    "                dp = nums[i]\n",
    "            if i == 1:\n",
    "                dp = nums[i]\n",
    "                b = nums[i]\n",
    "            if i == 2:\n",
    "                dp = nums[i] + nums[i-2]\n",
    "                c = dp\n",
    "            if i>2:\n",
    "                dp = max(a,b) + nums[i]\n",
    "                a = b\n",
    "                b = c\n",
    "                c = dp\n",
    "            ans = max(dp,ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def rob(self, nums: List[int]) -> int:\r\n",
    "        if not nums:return 0\r\n",
    "        n=len(nums)\r\n",
    "        \r\n",
    "        dp=[0]*(n+1)\r\n",
    "        dp[1]=nums[0]\r\n",
    "        for i in range(2,n+1):\r\n",
    "            dp[i]=max(dp[i-2]+nums[i-1],dp[i-1])\r\n",
    "\r\n",
    "        print(dp)\r\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # 不一定只隔一个房子\n",
    "        # f[i] = max(f[i-1],f[i-2]+v[i])\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        f,f1,f2 = 0,nums[0],0\n",
    "        for i in range(1,len(nums)):\n",
    "            f = max(f1,f2+nums[i])\n",
    "            f2 = f1\n",
    "            f1 = f\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        cur,pre=0,0\n",
    "        for num in nums:\n",
    "            cur,pre=max(cur,pre+num),cur\n",
    "        return cur "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        last, res = 0, 0\n",
    "        for n in nums:\n",
    "            last, res = res, max(last+n, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums: return 0\n",
    "        if len(nums) == 1: return nums[0]\n",
    "\n",
    "        dp1 = [0] * len(nums)\n",
    "        dp2 = [0] * len(nums)\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            dp1[i] = max(dp1[i-2]+nums[i], dp1[i-1])\n",
    "        \n",
    "        return max(dp1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def rob(self, nums):\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        d={}\n",
    "        def dfs(index,status):\n",
    "            if index>=n:\n",
    "                return 0\n",
    "            if (index,status) in d:\n",
    "                return d[index,status]\n",
    "            a,b,c = 0,0,0\n",
    "            if status == 0: # 如果上次没偷\n",
    "                a = dfs(index+1,status) # 选择还不偷 \n",
    "                c = dfs(index+1,1)+nums[index] # 选择偷 \n",
    "            if status: # 如果上次偷了，这次只能不偷\n",
    "                b = dfs(index+1,0)                \n",
    "            d[index,status] = max(a,b,c)\n",
    "            return d[index,status]\n",
    "        return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "cache = {}\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0: return 0\n",
    "        if len(nums) == 1: return nums[0]\n",
    "        key = tuple(nums)\n",
    "        if key not in cache:\n",
    "            cache[key] = max(\n",
    "                nums[0] + self.rob(nums[2:]),\n",
    "                self.rob(nums[1:])\n",
    "            )\n",
    "        return cache[key]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def rob(self, nums: List[int]) -> int:\n",
    "#         if not nums:\n",
    "#             return 0\n",
    "#         if len(nums) == 1:\n",
    "#             return nums[0]\n",
    "#         res = []\n",
    "#         for i in range(len(nums)):\n",
    "#             if i > 1 and i < len(nums) - 2:\n",
    "#                 res.append(nums[i] + self.rob(nums[:i-1]) + self.rob(nums[i+2:]))\n",
    "#             elif i <= 1:\n",
    "#                 res.append(nums[i] + self.rob(nums[i+2:]))\n",
    "#             else:\n",
    "#                 res.append(nums[i] + self.rob(nums[:i-1]))\n",
    "#         return max(res)\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        a =[]\n",
    "        for i in range(l):\n",
    "            a.append([-1]*l)\n",
    "        def abc(l, r):\n",
    "            if l > r:\n",
    "                return 0\n",
    "            if a[l][r] != -1:\n",
    "                return a[l][r]\n",
    "            if l == r:\n",
    "                a[l][l] = nums[l]\n",
    "                return nums[l]\n",
    "            \n",
    "            res = []\n",
    "            for i in range(l, r+1):\n",
    "                if i > l+1 and i < r-1:\n",
    "                    res.append(nums[i] + abc(l, i-2) + abc(i+2, r))\n",
    "                elif i <= l+1:\n",
    "                    res.append(nums[i] + abc(i+2, r))\n",
    "                else:\n",
    "                    res.append(nums[i] + abc(l, i-2))\n",
    "            a[l][r] = max(res)\n",
    "            return a[l][r]\n",
    "        res = abc(0, len(nums)-1)\n",
    "        # import pprint\n",
    "        # pprint.pprint(a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        # dp[0] = nums[0], dp[1] = max(num[1], num[0])\n",
    "        # dp[i] = max(nums[i] + f(i-2), f(i-1))\n",
    "        n = len(nums)\n",
    "\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return nums[0]\n",
    "\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0], nums[1])\n",
    "        for i in range(2, n):\n",
    "            dp[i] = max(nums[i] + dp[i-2], dp[i-1])\n",
    "\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        f0 = f1 = 0\n",
    "        for num in nums:\n",
    "            new_f = max(f0, f1 + num)\n",
    "            f1 = f0\n",
    "            f0 = new_f\n",
    "        return new_f\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(n):\n",
    "        #     if n < 0:\n",
    "        #         return 0\n",
    "        #     res = max(dfs(n - 1), dfs(n-2) + nums[n])\n",
    "        #     return res\n",
    "        # return dfs(n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        n = len(nums)\n",
    "        dp = [0]*(n+1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = nums[0]\n",
    "        for i in range(2,n+1):\n",
    "            dp[i] = max(dp[i-1],nums[i-1]+dp[i-2])\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        l = len(nums)\n",
    "        dp=[]\n",
    "        dp.append(0)\n",
    "        dp.append(nums[0])\n",
    "        for i in range(2,l+1):\n",
    "            dp.append(max(dp[i-1],nums[i-1] + dp[i-2]))\n",
    "\n",
    "        return dp[l]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            nonlocal res\n",
    "            if i<0:return 0\n",
    "            tmp = max(dfs(i-1),dfs(i-2)+nums[i])\n",
    "            res = max(res,tmp)\n",
    "            return tmp\n",
    "        dfs(n-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        @lru_cache()\n",
    "        def rob_(start):\n",
    "            if start < len(nums)-3:\n",
    "                planA = nums[start] + max(rob_(start+2+i) for i in range(len(nums)-2))\n",
    "                planB = nums[start+1] + max(rob_(start+3+i) for i in range(len(nums)-3))\n",
    "                return max(planA, planB)\n",
    "            elif start == len(nums)-1:\n",
    "                return nums[-1]\n",
    "            elif start == len(nums)-2:\n",
    "                return max(nums[-1], nums[-2])\n",
    "            elif start == len(nums)-3:\n",
    "                return max(nums[-1]+nums[-3], nums[-2])\n",
    "            else:\n",
    "                return 0\n",
    "        \n",
    "        return rob_(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        size = len(nums)\n",
    "        if size == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        first, second = nums[0], max(nums[0], nums[1])\n",
    "        for i in range(2, size):\n",
    "            first, second = second, max(first + nums[i], second)\n",
    "        \n",
    "        return second"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        max_value = float('-inf')\n",
    "        a, b = 0, 0\n",
    "        for num in nums:\n",
    "            curr_max = max(a + num, b)\n",
    "            a, b = b, curr_max\n",
    "            max_value = max(max_value, curr_max)\n",
    "        return max_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rob(self, nums: List[int]) -> int:\n",
    "        size = len(nums)\n",
    "        if size < 3:\n",
    "            return max(nums)\n",
    "        dp = [0]*(size)\n",
    "        dp[0] = nums[0]\n",
    "        dp[1] = max(nums[0],nums[1])\n",
    "        for i in range(2,size):\n",
    "            dp[i] = max(dp[i-1],dp[i-2]+nums[i])\n",
    "        return dp[size-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
